#include "Utils.h"

#include <eastl/vector.h>

const int OfsX[4] = { 0, 1, 0, -1 };
const int OfsY[4] = { -1, 0, 1, 0 };
const int RevOfsX[4] = { 0, -1, 0, 1 };
const int RevOfsY[4] = { 1, 0, -1, 0 };
const int RevDir[4] = { 2, 3, 0, 1 };

struct pos { int x, y; pos(int _x, int _y) : x(_x), y(_y) {} pos(const pos& p) : x(p.x),y(p.y) {} };

pos Dir(pos p, int dir)
{
	return pos(p.x + OfsX[dir], p.y + OfsY[dir]);
}

bool Valid(CoolMaze& maze, size_t x, size_t y)
{
	return x<maze.width&&y<maze.height;
}

MazeTile* GetNeighbour(CoolMaze& maze, pos curcell, int dir)
{
	pos neicell = Dir(curcell, dir);
	if (!Valid(maze,neicell.x,neicell.y)) return 0;
	return &maze(neicell.x,neicell.y);
}

void OpenWall(CoolMaze& maze, pos curcell, int dir)
{
	maze(curcell.x, curcell.y).Exits |= (1<<dir);
	GetNeighbour(maze, curcell, dir)->Exits |= (1<<RevDir[dir]);
}

void GenerateMaze(CoolMaze& maze, int sx, int sy)
{
	/// Reset
	maze.MapMethodPointer(&MazeTile::Reset);

	for (size_t y=0; y<maze.height; y++)
	{
		maze(0, y).Exits = 1<<LEFT;
		maze(maze.width-1, y).Exits = 1<<RIGHT;
	}
	for (size_t x=0; x<maze.width; x++)
	{
		maze(x, 0).Exits = 1<<UP;
		maze(x, maze.height-1).Exits = 1<<DOWN;
	}

	eastl::vector<pos> Unvisited;
	Unvisited.push_back(pos(sx,sy));
	pos curcell = pos(sx,sy);
	maze(sx,sy).Visited = true;
	maze(sx,sy).DistanceToStart = 0;
	while (Unvisited.size())
	{
		int unv = 0;
		for (int i=0; i<4; i++)
		{
			MazeTile* tile = GetNeighbour(maze,curcell,i);
			if (tile && !tile->Visited) unv++;
		}

		if (!unv)
		{
			curcell = Unvisited.back();
			Unvisited.pop_back();
			continue;
		}

		unv = rand()%unv;
		Unvisited.push_back(curcell);

		int i = 0;
		for (; i<4; i++)
		{
			MazeTile* newtile = GetNeighbour(maze,curcell,i);
			if (newtile && !newtile->Visited) unv--;
			if (unv < 0)
			{
				pos newcell = Dir(curcell,i);
				OpenWall(maze,curcell,i);
				maze(newcell.x, newcell.y).Visited = true;
				maze(newcell.x, newcell.y).DistanceToStart = maze(curcell.x, curcell.y).DistanceToStart+1;
				curcell = newcell;
				break;
			}
		}
	}
}

///************************************************************************/
/// Simplex Noise
/// Port of the Java implementation by Stefan Gustavson
///************************************************************************/

struct Grad
{
	float x,y,z;
	Grad(float xx, float yy, float zz) : x(xx), y(yy), z(zz) {}
};

static const Grad grad3[] = {Grad(1,1,0),Grad(-1,1,0),Grad(1,-1,0),Grad(-1,-1,0),
	Grad(1,0,1),Grad(-1,0,1),Grad(1,0,-1),Grad(-1,0,-1),
	Grad(0,1,1),Grad(0,-1,1),Grad(0,1,-1),Grad(0,-1,-1)};

static const short p[] = {151,160,137,91,90,15,
131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180};

// Skewing and unskewing factors for 2, 3, and 4 dimensions
static const float F2 = 0.5f*(sqrtf(3.0f)-1.0f);
static const float G2 = (3.0f-sqrtf(3.0f))/6.0f;
static const float F3 = 1.0f/3.0f;
static const float G3 = 1.0f/6.0f;
static const float F4 = (sqrtf(5.0f)-1.0f)/4.0f;
static const float G4 = (5.0f-sqrtf(5.0f))/20.0f;

static float dot(Grad g, float x, float y) {
	return g.x*x + g.y*y; }

static float dot(Grad g, float x, float y, float z) {
	return g.x*x + g.y*y + g.z*z; }

static short perm[512];
static short permMod12[512];
static bool permInit = false;

void InitPerm()
{
	if (permInit) return;
	permInit = true;

	for(int i=0; i<512; i++)
	{
		perm[i]=p[i & 255];
		permMod12[i] = (short)(perm[i] % 12);
	}
}

float Noise( float xin, float yin )
{
	InitPerm();
	float n0, n1, n2; // Noise contributions from the three corners
	// Skew the input space to determine which simplex cell we're in
	float s = (xin+yin)*F2; // Hairy factor for 2D
	int i = (int)floor(xin+s);
	int j = (int)floor(yin+s);
	float t = (i+j)*G2;
	float X0 = i-t; // Unskew the cell origin back to (x,y) space
	float Y0 = j-t;
	float x0 = xin-X0; // The x,y distances from the cell origin
	float y0 = yin-Y0;
	// For the 2D case, the simplex shape is an equilateral triangle.
	// Determine which simplex we are in.
	int i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
	if(x0>y0) {i1=1; j1=0;} // lower triangle, XY order: (0,0)->(1,0)->(1,1)
	else {i1=0; j1=1;}      // upper triangle, YX order: (0,0)->(0,1)->(1,1)
	// A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and
	// a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where
	// c = (3-sqrt(3))/6
	float x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords
	float y1 = y0 - j1 + G2;
	float x2 = x0 - 1.0f + 2.0f * G2; // Offsets for last corner in (x,y) unskewed coords
	float y2 = y0 - 1.0f + 2.0f * G2;
	// Work out the hashed gradient indices of the three simplex corners
	int ii = i & 255;
	int jj = j & 255;
	int gi0 = permMod12[ii+perm[jj]];
	int gi1 = permMod12[ii+i1+perm[jj+j1]];
	int gi2 = permMod12[ii+1+perm[jj+1]];
	// Calculate the contribution from the three corners
	float t0 = 0.5f - x0*x0-y0*y0;
	if(t0<0) n0 = 0.0f;
	else {
		t0 *= t0;
		n0 = t0 * t0 * dot(grad3[gi0], x0, y0);  // (x,y) of grad3 used for 2D gradient
	}
	float t1 = 0.5f - x1*x1-y1*y1;
	if(t1<0) n1 = 0.0f;
	else {
		t1 *= t1;
		n1 = t1 * t1 * dot(grad3[gi1], x1, y1);
	}
	float t2 = 0.5f - x2*x2-y2*y2;
	if(t2<0) n2 = 0.0f;
	else {
		t2 *= t2;
		n2 = t2 * t2 * dot(grad3[gi2], x2, y2);
	}
	// Add contributions from each corner to get the final noise value.
	// The result is scaled to return values in the interval [-1,1].
	return 70.0f * (n0 + n1 + n2);
}

float RandFloat( float low /*= 0.0f*/, float high /*= 1.0f*/ )
{
	return (float(rand())/float(RAND_MAX))*(high-low) + low;
}

Vec BezierQuadratic( float t, const Vec& p0, const Vec& p1, const Vec& p2 )
{
	float it = 1.0f-t;
	return p0*it*it + p1*2.0f*it*t + p2*t*t;
}

Vec BezierCubic( float t, const Vec& p0, const Vec& p1, const Vec& p2, const Vec& p3 )
{
	float it = 1.0f-t, it2 = it*it;
	float t2 = t*t;
	return it*it2*p0 + 3*it2*t*p1 + 3.0f*it*t2*p2 + t2*t*p3;
}

Vec CatmulRom(float t, const Vec& P0, const Vec& P1, const Vec& P2, const Vec& P3)
{
	return 0.5f *(	(2.0f * P1) + (-P0 + P2) * t + (2.0f*P0 - 5.0f*P1 + 4.0f*P2 - P3) * (t*t) + (-P0 + 3.0f*P1- 3.0f*P2 + P3) * (t*t*t));
}

void IMovementCost::Calculate(int startx, int starty, int mp, void* data)
{
	mStartX = startx;
	mStartY = starty;

	CalculateMovementCosts(startx, starty, mp, startx, starty, data);
}

void IMovementCost::CalculateMovementCosts( int x, int y, int MP, int px, int py, void* data )
{
	if (MP <= 0) return;

	/// every direction
	for (int i=0; i<4; i++)
	{
		/// calculate position and check if it is correct
		int mapx = x + OfsX[i];
		int mapy = y + OfsY[i];
		if (mapx==px && mapy==py) continue;
		if (!ValidPos(mapx, mapy)) continue;
		if (mapx == mStartX && mapy == mStartY) continue;

		MCTileInfo& tile = GetTile(mapx,mapy);
		int walkCost = GetWalkCost(data, tile.TileType);

		if ((MP-walkCost) < 0) continue;

		/// if the tile at that position is walkable, and we have enough MP to go there
		if (walkCost > 0 && walkCost <= MP)
		{
			/// check if the tile is already available for moving, if it is,
			/// check if it has a bigger MP, if so, set it to the current MP
			if (tile.avMP == 0)
			{
				tile.avMP = MP;
				tile.PX = x;
				tile.PY = y;
				SetTile(mapx, mapy, tile);

				CalculateMovementCosts(mapx,mapy, MP-walkCost, x, y, data);
			}
			if (tile.avMP < MP)
			{
				tile.avMP = MP;
				tile.PX = x;
				tile.PY = y;
				SetTile(mapx, mapy, tile);

				CalculateMovementCosts(mapx,mapy, MP-walkCost, x, y, data);
			}
		}
	}
}

eastl::string LoadFile(const char* filename)
{
	FILE* file = fopen(filename, "rb");
	fseek(file, 0, SEEK_END);
	size_t size = ftell(file);
	fseek(file, 0, SEEK_SET);
	eastl::string res;
	res.reserve(size+1);
	while (!feof(file))
	{
		char buf[1025];
		buf[fread(buf, 1, 1024, file)] = 0;
		res += buf;
	}
	fclose(file);
	return res;
}

float Ease(eEasing aType, float _t, float max_t, float start, float offset)
{
	if(_t > max_t)
	{
		return start + offset;
	}
	else if (_t < 0.0f)
	{
		return start;
	}

	float& t = _t;
	float& b = start;
	float& c = offset;
	float& d = max_t;

	float ts;
	float tc;

	switch(aType)
	{
	case EASING_NONE:
		t /= d;
		return b + c*t;

	case EASING_IN:
		ts = (t/=d)*t;
		return b + c*(ts*ts);

	case EASING_OUT:
		ts = (t/=d)*t;
		tc = ts*t;
		return b+c*(-1*ts*ts + 4*tc + -6*ts + 4*t);

	case EASING_INOUT:
		ts=(t/=d)*t;
		tc=ts*t;
		return b+c*(6*tc*ts + -15*ts*ts + 10*tc);

	case EASING_OUTIN:
		ts=(t/=d)*t;
		tc=ts*t;
		return b+c*(6*tc + -9*ts + 4*t);

	case EASING_BACKIN:
		ts=(t/=d)*t;
		tc=ts*t;
		return b+c*(2*ts*ts + 2*tc + -3*ts);

	case EASING_OUTBACK:
		ts=(t/=d)*t;
		tc=ts*t;
		return b+c*(-2*ts*ts + 10*tc + -15*ts + 8*t);

	case EASING_OUTELASTIC:
		ts=(t/=d)*t;
		tc=ts*t;
		return b+c*(56*tc*ts + -175*ts*ts + 200*tc + -100*ts + 20*t);

	case EASING_INELASTIC:
		ts=(t/=d)*t;
		tc=ts*t;
		return b+c*(56*tc*ts + -105*ts*ts + 60*tc + -10*ts);

	case EASING_OUTBOUNCE:
		if ((t/=d) < (1.0f/2.75f)) {
			return c*(7.5625f*t*t) + b;
		} else if (t < (2/2.75)) {
			return c*(7.5625f*(t-=(1.5f/2.75f))*t + .75f) + b;
		} else if (t < (2.5/2.75)) {
			return c*(7.5625f*(t-=(2.25f/2.75f))*t + .9375f) + b;
		} else {
			return c*(7.5625f*(t-=(2.625f/2.75f))*t + .984375f) + b;
		}

	case EASING_INBOUNCE:
		return c - Ease(EASING_OUTBOUNCE, d-t, d, 0, c) + b;

	case EASING_INOUTBOUNCE:
		if (t < d/2) return Ease(EASING_INBOUNCE, t*2, d, 0, c) * 0.5f + b;
		return Ease(EASING_OUTBOUNCE, t*2-d, d, 0, c) * 0.5f + c*0.5f + b;

	}

	return start;
}

void Tokenize( const char* input, eastl::vector<eastl::string>& tokens, const char* delims )
{
	const char* start = input;
	const char* cur = input;
	while (*cur)
	{
		cur = strpbrk(start, delims);
		if (!cur)
		{
			if (cur != start)
				tokens.push_back(start);
			return;
		} 
		else if (cur != start)
		{
			tokens.push_back(eastl::string(start, cur));
		}
		start = cur+1;
	}
}